首页
下载应用
提交文章
关于我们
🔥 热搜 🔥
1
百度
2
今日热点
3
微信公众平台
4
贴吧
5
opgg
6
dnf私服
7
百度贴吧
8
知乎
9
dnf公益服
10
百度傻逼
分类
社会
娱乐
国际
人权
科技
经济
其它
首页
下载应用
提交文章
关于我们
🔥
热搜
🔥
1
百度
2
今日热点
3
微信公众平台
4
贴吧
5
opgg
6
dnf私服
7
百度贴吧
8
知乎
9
dnf公益服
10
百度傻逼
分类
社会
娱乐
国际
人权
科技
经济
其它
这样的洞庭湖决堤,实在让人同情不起来
李尚福、魏凤和双双被拿下,与美国一份报告是否有关?
抗洪靠嘴,堵漏靠沙?印度官员真是绝了!
有的人走了,却永远活着
圈内疯传某谣言
生成图片,分享到微信朋友圈
2023年1月30日
2023年2月21日
2023年2月22日
2023年2月22日
2023年2月23日
2023年2月23日
2023年2月24日
2023年2月24日
2023年2月25日
2023年2月25日
2023年2月26日
2023年2月26日
2023年2月27日
2023年2月27日
2023年2月28日
查看原文
其他
比特币史话·91 | 随机(5): 生日攻击
Original
刘教链
刘教链
2023-01-30
收录于合集
#史话
102 个
#比特币
316 个
#中本聪
31 个
(生日攻击。图片来源于网络)
前情回顾:
比特币史话·86 | 压缩(4): 布隆过滤器
比特币史话·87 | 随机(1): 真伪随机数
比特币史话·88 | 随机(2): 脑钱包
比特币史话·89 | 随机(3): 破解索尼
比特币史话·90 | 随机(4): 香农熵
正文:
对比特币地址的攻击就是剑指其背后的资产控制权——私钥。在2010年7月25日中本聪在论坛中参与主题为“盗币”的讨论[1]时指出,比特币地址所采用的是160比特的哈希:
“比特币地址是唯一使用160位哈希的地方。其他一切都是SHA-256。计算公式为:”
“比特币地址 = RIPEMD-160(SHA-256(公钥))”
中本聪剖析了两种攻击方法。一种是碰撞攻击,另一种是分析攻击。前者是暴力破解,后者则是尝试找到哈希算法的弱点予以击破。
对于哈希函数的碰撞攻击,有一种称之为“生日攻击”(birthday attack)[2]的方法可以惊人地提高效率。能提高多少呢?对160比特的哈希进行生日攻击所需尝试的次数不是2的160次方(记为2^160),而是2的80次方(记为2^80),效率足足提高了2的80次方倍之多(2^80 * 2^80 = 2^160)。也因此哈希函数最低的安全位数不能低于160位,比特币所采用的RIPEMD-160是已知安全的哈希函数中最短的,也是最短的哈希函数里已知最安全的。在确保安全的前提下,长度短可以方便记录和沟通。
生日攻击所产生的与直觉有一点点相悖的原因在于组合爆炸。我们每个人的生日随机地分布在一年365天的某一天。请问一个有23位同学的班级里,有至少两人生日相同的概率是多少?答案是令人略感吃惊的50%概率,也就是有超过一半的可能性会有同学在同一天过生日。如果班级人数增加到50人,这个概率会上升到97%。
把生日看作是把每个人作为输入的、有365个输出值的哈希函数。发现哈希碰撞所需的计算次数并非正比于值空间大小,而是值空间大小的平方根。据说,量子计算机可以把这个效率进一步提高到值空间大小的立方根。只是由于实用化量子计算机迟迟没有问世,所以关于这一点,学界也有争议。
但是在攻击比特币地址背后的私钥这件事上,生日攻击的方法是不可用的,因为私钥是用户随机选取的,攻击者并不能自由选择私钥。正如中本聪在上述论坛帖子中所指出的那样,“如果可以使用生日攻击,则为2^80。你不能为此使用生日攻击,因此难度是完整的2^160比特。虽然,如果你尝试破解100万(2^20)个交易中的任何一个,则可以进行部分生日攻击 2^160/2^20 = 2^140。”
关于分析攻击,中本聪又写道,“如果我说错了,请纠正我(我会很高兴收回我说过的话),但在这种情况下,我认为很难对RIPEMD-160进行分析攻击。分析攻击预设了输入值的范围或模式进行尝试,这将大大增加发现碰撞的机会。在这里,你对RIPEMD-160的输入没有那种控制,因为输入是SHA-256的输出。如果分析攻击帮助你找到一个会产生碰撞的RIPEMD-160输入,然后你会做什么?你仍然必须使用SHA-256来输出该值,因此你仍然不得不去再破解SHA-256。”
最后中本聪总结道,“对于,RIPEMD-160(SHA-256(x))并不比单独的RIPEMD-160强。但是对于分析攻击,似乎必须同时对RIPEMD-160和SHA-256进行分析攻击。如果我错了,那么强度与RIPEMD-160相同,而SHA-256仅用作一轮密钥加固。”
【未完待续】(公众号:刘教链)
您可能也对以下帖子感兴趣
{{{title}}}
文章有问题?点此查看未经处理的缓存